#include "GreatUInt.h"
#include "FastUInt.h"
#include <iostream>
#include <sstream>
#include <iomanip>

//utility

static UInt StringToUInt(const std::string& i_temp)
{
	UInt temp=0;
	size_t i=0;
	while(i<i_temp.size())
	{
		temp*=10;
		temp+= i_temp.at(i) - '0';
		++i;
	}
	return temp;
}

//accessors

UInt GreatUInt::GetNumDigits() const
{
	UInt numDigits = (static_cast<UInt>(m_data.size()) - 1) * 9;
	UInt temp = m_data.back();
	while(temp)
	{
		++numDigits;
		temp/=10;
	}
	
	return temp;
}

UInt GreatUInt::GetDigit(const UInt i_digitNum) const
{
	static const UInt factors[9] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000};
	const UInt index = i_digitNum/9;
	
	if(index>=m_data.size())
		return 0;

	const UInt offset = i_digitNum%9;
	return (m_data[index]/factors[offset])%10;
}

UInt GreatUInt::DigitSum() const
{
	UInt result=0;
	for(Container::const_iterator it=m_data.begin(); it!=m_data.end(); ++it)
	{
		UInt temp = *it;
		while(temp)
		{
			result +=temp%10;
			temp/=10;
		}
	}
	return result;
}

bool GreatUInt::IsLessThan( const GreatUInt& i_that ) const
{
	const size_t thisDataSize = m_data.size(); 
	const size_t thatDataSize = i_that.m_data.size(); 
	if(thisDataSize < thatDataSize)return true;
	if(thisDataSize > thatDataSize)return false;

	size_t i=thisDataSize-1;
	while((m_data[i] == i_that.m_data[i]) && (i!=0))
		--i;
	return m_data[i] < i_that.m_data[i];
}

//cannot be inlined due to dependency to FastUInt interface
void GreatUInt::ToFastUInt( FastUInt& o_fastUInt ) const
{
	o_fastUInt.Assign(*this);
}

void GreatUInt::ToString( std::string& o_string ) const
{
	o_string.clear();
	std::ostringstream sstream;
	sstream << *this;
	o_string = sstream.str();
}

//modifiers

GreatUInt& GreatUInt::Assign(const std::string& i_string)
{
	if(i_string.empty())
		return SetZero();

	m_data.clear();

	size_t len = i_string.size();
	size_t offset = len%9;
	if(offset!=0)
	{
		std::string temp = i_string.substr(0,offset);
		m_data.push_front(StringToUInt(temp));
	}
	size_t i=0;
	while(offset + i*9 < len)
	{
		std::string temp = i_string.substr(offset+i*9,9);
		m_data.push_front(StringToUInt(temp));
		++i;
	}
	return *this;
}

GreatUInt& GreatUInt::Assign( const FastUInt& i_fastUInt )
{
	//TODO
	return SetInvalid();
}

GreatUInt& GreatUInt::operator++()
{
	size_t i=0;
	while(i<m_data.size() && m_data[i]==ALL_NINES)
	{
		m_data[i] = 0;
		++i;
	}
	if(i == m_data.size())
		m_data.push_back(1);
	else
		++m_data[i];
	
	return *this;
}

GreatUInt& GreatUInt::operator--()
{
	if(IsZero())
		return SetInvalid();
	
	size_t i=0;
	while(i<m_data.size() && m_data[i]==0)
	{
		m_data[i] = ALL_NINES;
		++i;
	}
	--m_data[i];
	if(m_data.back() == 0)
		m_data.pop_back();
	
	return *this;
}

GreatUInt& GreatUInt::operator+=(const UInt i_num)
{
	if(IsZero())
		return Assign(i_num);

	UInt report = 0;
	UInt64 result = i_num;
	result += m_data[0];
	report = static_cast<UInt>(result/MAX_ELEMENT_VALUE_64);
	m_data[0] = static_cast<UInt>(result%MAX_ELEMENT_VALUE_64);

	size_t i=1;
	while(i<m_data.size() && report!=0)
	{
		m_data[i] += report;
		report = m_data[i]/MAX_ELEMENT_VALUE;
		m_data[i] = m_data[i]%MAX_ELEMENT_VALUE;
		++i;
	}

	if(report)
		m_data.push_back(report);
	
	return *this;
}

GreatUInt& GreatUInt::operator+=(const GreatUInt& i_that)
{
	size_t i=0;
	UInt report=0;
	while(i<m_data.size() && i<i_that.m_data.size())
	{
		m_data[i] += i_that.m_data[i] + report;
		report = m_data[i]/MAX_ELEMENT_VALUE;
		m_data[i] = m_data[i]%MAX_ELEMENT_VALUE;
		++i;
	}
	if(i==m_data.size() && i<i_that.m_data.size())
	{
		while(i<i_that.m_data.size())
		{
			m_data.push_back(i_that.m_data[i] + report);
			report = m_data[i]/MAX_ELEMENT_VALUE;
			m_data[i] = m_data[i]%MAX_ELEMENT_VALUE;
			++i;
		}
		if(report!=0)
			m_data.push_back(report);
	}else if(i<m_data.size() && i==i_that.m_data.size()){
		while(i<m_data.size() && report)
		{
			m_data[i]+=report;
			report = m_data[i]/MAX_ELEMENT_VALUE;
			m_data[i] = m_data[i]%MAX_ELEMENT_VALUE;
			++i;
		}
		if(report!=0)
			m_data.push_back(report);
	}else{ //(i==m_data.size() && i==i_that.m_data.size())
		if(report!=0)
			m_data.push_back(report);
	}
	return *this;
}

GreatUInt& GreatUInt::operator-=(const UInt i_num)
{
	if(i_num==0)
		return *this;
	
	if(i_num>=MAX_ELEMENT_VALUE)
		return operator-=(GreatUInt(i_num));

	if(m_data[0] >= i_num)
	{
		m_data[0]-= i_num;
		return *this;
	}

	if(m_data.size() == 1)
		return SetInvalid();

	m_data[0] += MAX_ELEMENT_VALUE - i_num;
	size_t i=1;
	while(m_data[i]==0)
	{
		m_data[i] = ALL_NINES;
		++i;
	}
	--m_data[i];
	return *this;
}

GreatUInt& GreatUInt::operator-=(const GreatUInt& i_that)
{
	if(*this<i_that)
		return SetInvalid();

	if(*this==i_that)
		return SetZero();
	
	UInt sub = 0;
	size_t i;
	for(i=0; i<i_that.m_data.size(); ++i)
	{
		const UInt totalSub = i_that.m_data[i] + sub;
		if(m_data[i] < totalSub)
		{
			m_data[i] += MAX_ELEMENT_VALUE - totalSub;
			sub = 1;
		}else{
			m_data[i] -= totalSub;
			sub = 0;
		}
	}
	if(sub)
	{
		while(m_data[i]==0)
		{
			m_data[i] = ALL_NINES;
			++i;
		}
		--m_data[i];
	}

	while(m_data.back()==0)
		m_data.pop_back();

	return *this;
}

GreatUInt& GreatUInt::operator*=(const GreatUInt& i_that)
{
	GreatUInt result;
	for(size_t i=0; i<i_that.m_data.size(); ++i)
	{
		GreatUInt temp(*this);
		temp*=i_that.m_data.at(i);
		for(size_t j=0; j<i; ++j)
			temp.m_data.push_front(0);
		result+=temp;
	}
	*this = result;
	return *this;
}

GreatUInt& GreatUInt::operator*=(const UInt i_factor)
{
	if(i_factor==0)
		return SetZero();

	Container temp;
	UInt report = 0;
	UInt64 result;
	for(size_t i=0; i<m_data.size(); ++i)
	{
		result = i_factor;
		result *= m_data.at(i);
		result += report;
		const UInt data = static_cast<UInt>(result%MAX_ELEMENT_VALUE_64);
		temp.push_back(data);
		report = static_cast<UInt>(result/MAX_ELEMENT_VALUE_64);
	}
	if(report!=0)
		temp.push_back(report);

	m_data = temp;
	return *this;
}

GreatUInt& GreatUInt::operator&=(const GreatUInt& i_that)
{
	//inefficient
	FastUInt fast_first(*this);
	fast_first &= FastUInt(i_that);
	return Assign(fast_first);
}

GreatUInt& GreatUInt::operator|=(const GreatUInt& i_that)
{
	//inefficient
	FastUInt fast_first(*this);
	fast_first |= FastUInt(i_that);
	return Assign(fast_first);
}

GreatUInt& GreatUInt::operator^=(const GreatUInt& i_that)
{
	//inefficient
	FastUInt fast_first(*this);
	fast_first ^= FastUInt(i_that);
	return Assign(fast_first);
}

GreatUInt& GreatUInt::operator<<=(const UInt i_factor)
{
	//inefficient
	FastUInt fast_first(*this);
	fast_first <<= i_factor;
	return Assign(fast_first);
}

GreatUInt& GreatUInt::operator>>=(const UInt i_factor)
{
	//inefficient
	FastUInt fast_first(*this);
	fast_first >>= i_factor;
	return Assign(fast_first);
}

GreatUInt& GreatUInt::DivWithRem(const GreatUInt& i_toBeDivided, const GreatUInt& i_divisor, bool i_storeQuotient, GreatUInt* o_other)
{
	//TODO: maybe it's better to perform the division in FastUInt and then go back there...
	return *this;
}
//
//GreatUInt& GreatUInt::DivWithRemainder(const GreatUInt& i_divisor, GreatUInt& o_remainder)
//{
//	if(this==&o_remainder)
//		return SetInvalid();
//	
//	if(i_divisor.IsZero())
//	{
//		o_remainder.SetInvalid();
//		return SetInvalid();
//	}
//
//	if(this==&i_divisor)
//	{
//		o_remainder.SetZero();
//		return SetOne();
//	}
//
//	if(IsLessThan(i_divisor))
//	{
//		Swap(o_remainder);
//		return SetZero();
//	}
//
//	// o_remainder = 
//	o_remainder.Mul(operator/=(i_divisor),i_divisor).Sub(*this,o_remainder);
//	//TODO
//	return *this;
//}

GreatUInt& GreatUInt::ApplyExp(const UInt i_exp)
{
	if(i_exp==0)
		return SetOne();
	
	GreatUInt temp(*this);
	for(UInt i=1; i<i_exp; ++i)
	{
		operator*=(temp);
	}
	
	return *this;
}

// non members

std::ostream& operator<<(std::ostream& os, const GreatUInt& i_data)
{
	typedef GreatUInt::Container::const_reverse_iterator Iter;
	Iter it = i_data.m_data.rbegin();
	Iter end = i_data.m_data.rend();
	if(it!=end)
	{
		os << *it;		
		++it;
	}
	while(it!=end)
	{
		os << std::setw(9) << std::setfill('0') << *it;		
		++it;
	}
	os.clear();
	return os;
}

